#define _CRT_SECURE_NO_WARNINGS 1
//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，
//该指针可以指向链表中的任何节点或空节点。
//
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，
//其中每个新节点的值都设为其对应的原节点的值。
//新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
//并使原链表和复制链表中的这些指针能够表示相同的链表状态。
//复制链表中的指针都不应指向原链表中的节点 。
//
//例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。
//那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//
//返回复制链表的头节点。
//
//用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个[val, random_index] 表示：
//
//val：一个表示 Node.val 的整数。
//random_index：随机指针指向的节点索引（范围从 0 到 n - 1）；如果不指向任何节点，则为  null 。
//你的代码 只 接受原链表的头节点 head 作为传入参数。
//输入：head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
//输出： [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
	struct ListNode* random;
};
void SLTPrint(struct ListNode* phead)
{
	struct ListNode* cur = phead;//current当前
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
//法一，先链接复制节点，之后原链表和复制链表依次用两个指针遍历，确定random
//struct ListNode* copyRandomList(struct ListNode* head)
//{
//    struct ListNode* cur = head;
//    struct ListNode* tail = NULL;
//    struct ListNode* newhead = NULL;
//    while (cur)
//    {
//        struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
//        if (tail == NULL)
//        {
//            tail = newnode;
//            newhead = newnode;
//        }
//        else
//        {
//            tail->next = newnode;
//            tail = tail->next;
//        }
//        newnode->val = cur->val;
//        newnode->next = NULL;
//        newnode->random = NULL;
//        cur = cur->next;
//    }
//    struct ListNode* slow = head;
//    struct ListNode* fast = head;
//    struct ListNode* newslow = newhead;
//    struct ListNode* newfast = newhead;
//    while (newslow)
//    {
//        while (fast == slow->random)
//        {
//            newslow->random = newfast;
//            newslow = newslow->next;
//            newfast = newhead;
//            slow = slow->next;
//            fast = head;
//            if (slow == NULL)
//                break;
//        }
//        newfast = newfast->next;
//        fast = fast->next;
//    }
//    return newhead;
//}
//法二，1，原链表中，每个复制节点插入到对应原节点后面
//2，控制复制节点的random，
//如果原节点random指向NULL,复制节点random指向NULL
//否则复制节点random指向原节点random指向节点的next
struct ListNode* copyRandomList(struct ListNode* head)
{
    if(head==NULL)return head;
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newnode->next = cur->next;
        cur->next = newnode;
        newnode->val = cur->val;
        newnode->random = NULL;
        cur = cur->next->next;
    }
    cur = head;
    while (cur)
    {
        if (cur->random == NULL)
        {
            cur->next->random = NULL;
        }
        else
        {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    cur = head->next;
    struct ListNode* newhead = cur;
    while (cur)
    {
        if (cur->next != NULL)
        {
            cur->next = cur->next->next;
            cur = cur->next;
        }
        else
        {
            cur = cur->next;
        }
    }
    return newhead;
}
int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    //struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));

    struct ListNode* head;
    head = n1;

    n1->val = 7;
    n1->next = n2;
    n1->random = NULL;

    n2->val = 13;
    n2->next = n3;
    n2->random = n1;

    n3->val = 11;
    n3->next = n4;
    n3->random = n5;

    n4->val = 10;
    n4->next = n5;
    n4->random = n3;

    n5->val = 1;
    n5->next = NULL;
    n5->random = n1;

    SLTPrint(head);
    struct ListNode* ret = copyRandomList(head);
    SLTPrint(ret);
}
